package com.practice.misc;

public class TreeBuilder {
	public final static void main(String[] args) {
		String inorder = "857496";
		String bfs = "789546";
		Node root = new TreeBuilder().run(inorder, bfs);
		System.out.println("end");
	}	
	
	private Node run(String inorder, String bfs) {
		if (bfs.length() == 0) return null;
		char root = bfs.charAt(0);
		int index = inorder.indexOf(root);
		
		Node node = new Node();
		node.value = root;
		
		String lIn = inorder.substring(0, index);
		String rIn = inorder.substring(index+1);
		
		StringBuffer lBfs = new StringBuffer();
		StringBuffer rBfs = new StringBuffer();
		
		for (char c : bfs.toCharArray()) {
			if (c == root) continue;
			if (lIn.indexOf(c) >= 0) {
				lBfs.append(c);
			}
			else {
				rBfs.append(c);
			}
		}
		
		node.left = run(lIn, lBfs.toString());
		node.right = run(rIn, rBfs.toString());
		return node;
	}
	
	private class Node {
		Node left;
		Node right;
		char value;
	}
}
